package searchMatrix;

/**
 * @author limaosheng
 * @create 2021-10-26 15:16
 * @desc 搜索二维矩阵 II
 * <p>
 * 题目：
 * 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
 * 每行的元素从左到右升序排列。
 * 每列的元素从上到下升序排列。
 * <p>
 * 提示：
 * m == matrix.length
 * n == matrix[i].length
 * 1 <= n, m <= 300
 * -10的9次方<= matrix[i][j] <= 10的9次方
 * -10的9次方<= target <= 10的9次方
 * <p>
 * 测试用例：
 * 输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
 * 输出：true
 * 输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
 * 输出：false
 */
public class SearchMatrix1 {

    public static void main(String[] args) {
        int[][] matrix = {{1, 4, 7, 11, 15}, {2, 5, 8, 12, 19}, {3, 6, 9, 16, 22}, {10, 13, 14, 17, 24}, {18, 21, 23, 26, 30}, {19, 22, 25, 27, 31}};
        SearchMatrix1 searchMatrix = new SearchMatrix1();
        for (int i = 0; i < 33; i++) {
            System.out.println("值：" + i + ",结果：" + searchMatrix.searchMatrix(matrix, i));
        }
    }

    /**
     * 行列二分法查找
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        //获取行列长度m,n，减1后表示行列下标最大值
        int m = matrix.length - 1;
        int n = matrix[0].length - 1;
        //判断目标值是否在数组最小到数组最大的范围内
        if (target < matrix[0][0] || target > matrix[m][n]) {
            return false;//不在范围内，直接返回false
        }
        //只有一行数组
        if(m == 0){
            return checkSercher(0, n, matrix[0], target);
        }
        //在范围内，数组搜寻是否有满足的目标值
        return binarySercher(0, m, matrix, target, m, n);
    }

    /**
     * 二分法查找（递归实现），目标，找到一行，目标值大于该行最小，小于该行最大，然后往前后行寻找是否存在目标值
     *
     * @param start  开始行下标
     * @param end    结束行下标
     * @param matrix
     * @param target
     * @param m      行最大下标
     * @param n      列最大下标
     * @return 二分定位中间行，判断：
     * 1、目标值小于该行最小，表示目标值不可能出现在该行以及该行以后，往前继续二分法查找
     * 2、目标值大于该行最大，表示目标值不可能出现在该行以及该行之前，往后继续二分法查找
     * 3、目标值大于该行最小，小于该行最大
     * 3.1、判断该行是否包含目标值，包含，返回true，未包含，则往3.2
     * 3.2、往该行之前的行一行一行寻找，直到出现目标值或者待查找的行最大值小于目标值，出现目标值，返回true，否则往3.3
     * 3.3、往该行之后的行一行一行寻找，直到出现目标值或者待查找的行最小值大于目标值，出现目标值，返回true，否则返回false
     */
    private boolean binarySercher(int start, int end, int[][] matrix, int target, int m, int n) {
        //二分法计算待校验行下标
        int middle = (end - start) / 2 + start;
        //获取待校验行
        int[] check = matrix[middle];
        //判断
        if (target < check[0]) {
            //目标值小于该行最小
            end = middle;//往前查找，则end为middle
            //行数相差1，因为当前行已判断，则只有前一行数组需要判断是否存在目标值
            if (end - start == 1) {
                return checkSercher(0, n, matrix[start], target);
            }
            //继续二分法
            return binarySercher(start, end, matrix, target, m, n);
        } else if (target > check[n]) {
            //目标数大于该行最大
            start = middle;//往后查找，则start为middle
            //行数相差1，因为当前行已判断，则只有后一行数组需要判断是否存在目标值
            if (end - start == 1) {
                return checkSercher(0, n, matrix[end], target);
            }
            //继续二分法
            return binarySercher(start, end, matrix, target, m, n);
        } else {
            //判断当前行是否存在目标值
            if (checkSercher(0, n, check, target)) {
                return true;
            } else {
                //往前寻找目标值
                if (before(matrix, middle, target, n)) {
                    return true;
                }
                //往后寻找目标值
                return after(matrix, middle, target, m, n);
            }
        }
    }

    /**
     * 待校验数组为有序数组，二分法判断（递归实现）
     *
     * @param start  开始下标
     * @param end    结束下标
     * @param check  待校验数组
     * @param target 目标值
     * @return
     */
    private boolean checkSercher(int start, int end, int[] check, int target) {
        //待校验数组长度为1
        if(start == end){
            return check[start] == target;
        }
        //二分法计算待校验数下标
        int mid = (end - start) / 2 + start;
        //待校验数字
        int checkNum = check[mid];
        if (checkNum == target) {
            //相等直接返回true
            return true;
        } else if (target < checkNum) {
            //目标值小于待校验数字，往前寻找
            end = mid;
            //下标相差1，判断前一个数字是否符合
            if (end - start == 1) {
                return check[start] == target;
            }
            //继续二分法
            return checkSercher(start, end, check, target);
        } else {
            //目标值大于待校验数字，往后寻找
            start = mid;
            //下标相差1，判断后一个数字是否符合
            if (end - start == 1) {
                return check[end] == target;
            }
            //继续二分法
            return checkSercher(start, end, check, target);
        }
    }

    /**
     * 递归往前寻找目标值
     *
     * @param matrix
     * @param current 已校验行，需减1后获取下一个待校验行
     * @param target
     * @param n       列最大下标
     * @return
     */
    private boolean before(int[][] matrix, int current, int target, int n) {
        //行下标最小为0，为0则结束
        if (current == 0) {
            return false;
        }
        //前一行数组
        int[] check = matrix[current - 1];
        //目标数大于待检行最大，结束往前寻找
        if (target > check[n]) {
            return false;
        }
        if (checkSercher(0, n, check, target)) {
            //寻找目标值成功则返回
            return true;
        } else {
            //继续往前寻找
            return before(matrix, current - 1, target, n);
        }
    }

    /**
     * 递归往后寻找目标值
     *
     * @param matrix
     * @param current 已校验行，需加1后获取下一个待校验行
     * @param target
     * @param m       行最大下标
     * @param n       列最大下标
     * @return
     */
    private boolean after(int[][] matrix, int current, int target, int m, int n) {
        //行下标最大为m，为m则结束
        if (current == m) {
            return false;
        }
        //后一行数组
        int[] check = matrix[current + 1];
        //目标数小于待检行最小，结束往后寻找
        if (target < check[0]) {
            return false;
        }
        if (checkSercher(0, n, check, target)) {
            //寻找目标值成功则返回
            return true;
        } else {
            //继续往前寻找
            return after(matrix, current + 1, target, m, n);
        }
    }
}
